package main

import (
	"fmt"
	"math"
)

func main() {
	fmt.Println(minDepth(&TreeNode{
		Val: 3,
		Right: &TreeNode{
			Val: 20,
			Left: &TreeNode{
				Val: 15,
			},
			Right: &TreeNode{
				Val: 7,
			},
		},
	}))
}

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func minDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}
	if root.Left == nil && root.Right == nil {
		return 1
	} else if root.Left == nil {
		return minDepth(root.Right) + 1
	} else if root.Right == nil {
		return minDepth(root.Left) + 1
	} else {
		left := minDepth(root.Left)
		right := minDepth(root.Right)
		return int(math.Min(float64(left), float64(right))) + 1
	}

}

func minDepth2(root *TreeNode) int {
	if root == nil {
		return 0
	}
	level := []*TreeNode{root}
	height := 0
	for lenTmp := len(level); lenTmp != 0; lenTmp = len(level) {
		height += 1
		for _, v := range level {
			if v.Left == nil && v.Right == nil {
				return height
			} else if v.Left == nil {
				level = append(level, v.Right)
			} else if v.Right == nil {
				level = append(level, v.Left)
			} else {
				level = append(level, v.Left, v.Right)
			}
		}
		level = level[lenTmp:]
	}
	return height
}
